//2386.找出数组的第K大和
//https://leetcode.cn/problems/find-the-k-sum-of-an-array/?envType=daily-question&envId=2024-03-09
class Solution {
public:
    long long kSum(vector<int>& nums, int k) {
        //2,4,-2
        //开始拍列
        //上方为选择前面的数
        //下方为不选则前面的数
        //      4
        //  6   0
        //2
        //  4   2
        //     -2

        //先求最大和 再减去第k-1个小和
        long long sum = 0;
        for(int& n:nums)
        {
            //加上所有正数
            if(n > 0) sum += n;
            //取反所有负数 方便取小和
            else n = -n;
        }
        //将数组排序 以计算最小和
        sort(nums.begin(),nums.end());

        //存储 第k-i的和 以及当前数的下标 每次取最小的数 然后选择取后面的数和不取前面的数
        priority_queue<pair<long long,int>,deque<pair<long long,int>>,greater<pair<long long,int>>> pq;
        pq.emplace(0,0);
        while(--k) //取k-1次最小和
        {
            //弹出当前最小数
            auto [s,i] = pq.top(); pq.pop();
            if(i < nums.size())
            {
                //将当前最小的数加入 并记录下一个数
                //选择前面的数
                pq.emplace(s+nums[i],i+1);
                //不选前面的数
                if(i) pq.emplace(s+nums[i]-nums[i-1],i+1);
            }
        }
        return sum-pq.top().first;
    }
};